#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define max 20
#define length 50
#define big 999
typedef struct
{
	char v[max];
}vnode;
typedef struct
{
	int vnum,anum;
	vnode vs[max];
	int as[max][max];
}tu;
int visited[max];
int geti(tu * g,char a[])
{
	int i;
	for(i=0;i<g->vnum ;i++){
		if(strcmp(a,g->vs [i].v )==0)
			return i;
	}
}
void cre_tu(tu * g)
{
	scanf("%d%d",&g->vnum ,&g->anum );
	int i;
	for(i=0;i<g->vnum ;i++){
		scanf("%s",g->vs [i].v );
	}
	int j;
	for(i=0;i<g->vnum ;i++){
		for(j=0;j<g->vnum ;j++){
			g->as [i][j]=big;
		}
	}
	char a[max];
	char b[max];
	int weight,ia,ib;
	for(i=0;i<g->anum ;i++){
		scanf("%s%s%d",a,b,&weight);
		ia=geti(g,a);
		ib=geti(g,b);
		g->as [ia][ib]=weight;
		g->as [ib][ia]=weight;
	}
}
void print_tu(tu * g)
{
	int i,j;
	for(i=0;i<g->vnum ;i++){
		for(j=0;j<g->vnum ;j++){
			if(g->as [i][j]==big)
				printf("    0");
			else
				printf("%5d",g->as [i][j]);
		}
		printf("\n");
	}
}
void Shen(tu * g,char s[])
{
	int is;
	is=geti(g,s);
	visited[is]=1;
	printf("%s ",g->vs [is].v );
	int k;
	for(k=0;k<g->vnum ;k++){
		if(visited[k]==0&&g->as [is][k]!=big)
			Shen(g,g->vs [k].v );
	}
}
void shen(tu * g,char s[])
{
	int i;
	for(i=0;i<g->vnum ;i++)
		visited[i]=0;
	Shen(g,s);
	printf("\n");
}
int dui[length];
int front,rear;
void Guang(tu * g,char s[])
{
	int is;
	is=geti(g,s);
	if(visited[is]==0){
	visited[is]=1;
	printf("%s ",s);
	dui[rear]=is;
	rear++;
	}
	int i;
	for(i=0;i<g->vnum ;i++){
		if(visited[i]==0&&g->as [is][i]!=big){
			visited[i]=1;
			printf("%s ",g->vs [i].v );
			dui[rear]=i;
			rear++;
		}
	}
	if(front!=rear){
		is=dui[front];
		front++;
		Guang(g,g->vs [is].v );
	}
}
void guang(tu * g,char s[])
{
	int i;
	for(i=0;i<g->vnum ;i++){
		visited[i]=0;
	}
	front=0;
	rear=0;
	for(i=0;i<length;i++)
		dui[i]=0;
	Guang(g,s);
	printf("\n");
}
typedef struct{
	int w;
	int i;
}flag;
void prim(tu * g,char s[])
{
	int i;
	for(i=0;i<g->vnum ;i++){
		visited[i]=0;
	}
	flag flags[max];
	for(i=0;i<g->vnum ;i++){
		flags[i].w =g->as [0][i];
		if(flags[i].w ==big)
			flags[i].i =-1;
		else
			flags[i].i =0;
	}
	visited[0]=1;
	int bigger,biggerpos,smaller,smallerpos;
	for(int n=1;n<g->vnum ;n++){
		for(i=0;i<g->vnum ;i++){
			if(visited[i]==0){
				if(flags[i].w >flags[flags[i].i ].w )
				{bigger=flags[i].w ;
				biggerpos=i;
				smaller=flags[flags[i].i ].w ;
				smallerpos=flags[flags[i].i ].i ;
				}
				else
				{bigger=flags[flags[i].i ].w ;
				biggerpos=flags[flags[i].i ].i ;
				smaller=flags[i].w ;
				smallerpos=flags[i].i ;
				}
				if(biggerpos!=-1&&g->as [n][i]<bigger){
					flags[biggerpos].w =g->as [n][i];
					if(biggerpos==i)
						flags[biggerpos].i =n;
					else
						flags[biggerpos].i =i;
				}
				else if(g->as [n][i]<smaller){
					flags[smallerpos].w =g->as [n][i];
					if(biggerpos==i)
						flags[smallerpos].i =n;
					else
						flags[smallerpos].i =i;
				}
			}
		}
		visited[n]=1;
	}
}
int main()
{
	tu g;
	char x;
	char s[max];
	while(1){
		scanf("%c",&x);
		switch(x){
		case'c':
			cre_tu(&g);
			break;
		case'o':
			print_tu(&g);
			break;
		case's':
			scanf("%s",s);
			shen(&g,s);
			break;
		case'g':
			scanf("%s",s);
			guang(&g,s);
			break;
		case'p':
			scanf("%s",s);
			prim(&g,s);
			break;
		case'q':
			printf("end\n");
			exit(0);
			break;
		default:
			break;
		}//switch
	}//while
}
/*
5 7
A B C D E
A B 100
A C 30
A E 10  
B C 25
B D 10
C D 20
D E 50
*/